package tree;

import com.sun.source.tree.Tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "吴用");
        TreeNode node3 = new TreeNode(3, "卢俊义");
        TreeNode node4 = new TreeNode(4, "林冲");
        TreeNode node5 = new TreeNode(5, "关胜");

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

       /* System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();


        System.out.println("先序查找");
        TreeNode resNode = binaryTree.preOrderSearch(6);
        if (resNode != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的节点", 6);
        }*/
        System.out.println("先序遍历");
        binaryTree.preOrder();
        binaryTree.delNode(1);
        System.out.println("删除后");
        binaryTree.preOrder();
    }
}

class BinaryTree {
    private TreeNode root;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //删除节点
    public void delNode(int no) {
        if (root == null) {
            System.out.println("二叉树为空");
            return;
        }
        if (root.getNo() == no) {
            root = null;
            return;
        }
        root.delNode(no);
    }

    //前序遍历
    public void preOrder() {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    //后序遍历
    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    //先序查找
    public TreeNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public TreeNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public TreeNode postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
}

class TreeNode {
    private int no;
    private String name;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //删除节点 规则：如果是叶子节点 直接删 如果不是叶子节点 带着树一起删除
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //左右节点都不是
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

    //前序遍历
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.postOrder();
        }

        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }

    //前序查找
    public TreeNode preOrderSearch(int no) {
        //先对比当前节点
        if (this.no == no) {
            return this;
        }
        TreeNode resNode = null;
        //递归向左子树前序查找
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
            if (resNode != null) {
                return resNode;
            }
        }
        //递归向右子树前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
            if (resNode != null) {
                return resNode;
            }
        }
        return null;
    }

    //中序查找
    public TreeNode infixOrderSearch(int no) {
        //递归向左子树前序查找
        if (this.left != null) {
            TreeNode leftNode = this.left.infixOrderSearch(no);
            if (leftNode != null) {
                return leftNode;
            }
        }
        //先对比当前节点
        if (this.no == no) {
            return this;
        }
        //递归向右子树前序查找
        if (this.right != null) {
            TreeNode rightNode = this.right.infixOrderSearch(no);
            if (rightNode != null) {
                return rightNode;
            }
        }
        return null;
    }

    //后序查找
    public TreeNode postOrderSearch(int no) {
        //递归向左子树前序查找
        if (this.left != null) {
            TreeNode leftNode = this.left.postOrderSearch(no);
            if (leftNode != null) {
                return leftNode;
            }
        }
        //递归向右子树前序查找
        if (this.right != null) {
            TreeNode rightNode = this.right.postOrderSearch(no);
            if (rightNode != null) {
                return rightNode;
            }
        }
        //对比当前节点
        if (this.no == no) {
            return this;
        }
        return null;
    }
}

